Distributed processing is used herein to describe systems in which a plurality of independent signal processing cells interact to perform a multiplicity of signal processing functions. In such systems, neighboring processors are typically interconnected to enable communication between one another. However, such neighborhood communication between processors represents only a portion of the processor communication that may be required in a distributed processing system. Thus, it may also be necessary to provide means to enable any processor in the system to communicate with any other processor. One way to enable such communication between other than neighboring processors, is to provide a separate, global communication network.
The size and complexity of such a global network is a direct function of the number of processing cells in the processing system. Processing system design can be characterized as ranging from a coarse grain to a fine grain design. A coarse grain design is one in which a relative few (e.g., 10's to 100's) large, relatively complex processors are used. At the opposite extreme, a fine grain design is one in which a large number (e.g., tens of thousands) of small, relatively simple processors are used. Thus in a coarse grain design, a simple global communication network would suffice to enable the relative few processors therein to communicate with one another. However, for a processing system with a fine grain design, a large, complex global network is required to achieve full communication between all processors.
A basic building block of such a communication network is the routing node. A routing node is an autonomous switching element through which a switching operation directs a received message signal to a selected output of the routing node. Thus, the individual processors communicate with one another through the routing nodes of the global network. In order to form the network, the routing nodes can be interconnected to form a variety of different communication network topologies. Examples of such network topologies include grids, omega networks, toruses and trees. The choice of topology affects the number of routing nodes required, number of interconnections between routing nodes, speed of communication through the network and the facility with which different forms of message signals are processed on the distributed processing system. One design objective present in the selection of a network topology is the minimization of transmission time through the communication network. Further, the need to minimize transmission time becomes more critical in a large communication network implemented for a processing system having a fine grain design.
A variety of routing algorithms can be used for transmitting message signals through global communication networks. With respect to a number of such algorithms, a portion of the message signal identifies its desired destination. For example where the message signal is in bit-serial form, a plurality of bits in the message signal determine the route of the message through the network to the desired destination. The route length through the network is measured in part by the number of routing nodes through which the message signal is transmitted. Thus, as the communication network increases in complexity, the number of routing nodes through which the message signal is directed, increases. Further, for a bit-serial message signal, the number of bits required to identify the desired destination also increases with network complexity.
The transmission of the destination portion bits of a bit-serial message signal requires a finite amount of transmission time which is not used to transmit actual data. Where the message signal carries a destination portion, each routing node through which the signal is transmitted directs the signal to a selected routing node output in response to the destination portion bits. However, in the course of transmitting the message signal, each routing node must transmit all of the subsequent destination portion bits. It is thus desirable to minimize the transmission time attributable to the destination portion bits. Additionally, where a particular route through the global network is frequently utilized, it is desirable to eliminate the need to transmit the destination bits for each message transmission over the particular route subsequent to an initial transmission.